Computer systems such as a typical desktop personal computer (PC) or workstation generally use a frame buffer to store image data for each picture element on a display monitor (CRT or LCD). Recently increases in network bandwidth have made the implementation of remote video frame buffers possible even for graphically intensive and high frame rate displays. Functionally, each picture element on the display's screen has a corresponding instance of image data commonly referred to as a pixel. When used remotely the frame buffer is connected to the computing and rendering engines of a video display system via a local area network (LAN) connection. At present, a typical LAN is composed of nodes connected by network links operating at a theoretical maximum of approximately 100 or 1000 megabits per second. Since all network applications share the bandwidth, only a fraction of this bandwidth is available for a given application. Thus, the data transmitted to the remote video frame buffer must be compressed to fit within the available network bandwidth and be able to adapt to changing availability of network bandwidth as the aggregate network load changes.
The efficiency of the compression algorithm used for such a purpose depends on the ratio of compressed data size to raw data size, as well as the speed at which compression and decompression can be performed. Typically, compression algorithms are tuned for special purpose use cases such as image compression, which makes use of the assumption that pixel gradients within the image are small, solid color rendered images, which makes use of the assumption that large blocks of similar pixel values are located in close proximity on the screen. These algorithms are generally efficient for narrowly tailored applications but may be very ineffectual, inefficient, and inadequate for other applications. For example, JPEG and MPEG image compression is efficient for photographic images but not for line drawings. This means that for a mixed video display composed of images, line drawings, and solid color fills, a single compression algorithm such as JPEG or MPEG is not efficient. On the other hand, simple vector graphics primitives can efficiently encode line drawings but are inefficient for encoding photographic images or videos. Thus, knowledge of the gross spatial characteristics of the image permits selection of an optimal compression algorithm.
Video streams are sequences of static images which when displayed in sequence produce motion picture video. Depending on the type of image displayed, additional compression efficiency may be gained by making use of knowledge about the general behavior of the images close to one another in the sequence. This technique is called inter-frame compression. For example, MPEG video compression is efficient for compressing video streams in which subsequent images differ only by incremental motion of objects from one image frame to the next. However, MPEG compression is typically a computationally expensive operation due to the fact that the compression algorithm must perform exhaustive searches for portions of the image that are in motion. If these “motion vectors” were known in advance, MPEG compression would be much less difficult to execute. In summary, knowledge of the gross temporal characteristics of the video stream, which are computationally expensive to deduce, after the stream has been produced would greatly aid the computational efficiency of the compression algorithm.
For the reasons stated above, and for other reasons stated below which will become apparent to those skilled in the art upon reading and understanding the present specification, there is a need in the art for computationally efficient system for compressing data. There is also a need for an improved system and method for increasing the throughput of a communication channel.